import sortedcontainers


class ExamRoom(object):

    def __init__(self, n):
        """
        :type n: int
        """
        self.n = n
        self.st = sortedcontainers.SortedList()
        self.space = sortedcontainers.SortedList()

    def seat(self):
        """
        :rtype: int
        """
        if not self.st:
            self.st.add(0)
            self.space.add([- (self.n - 1), 0])
            return 0
        node = self.space.pop(0)
        if node[1] < 0:
            self.st.add(0)
            if self.st[1] - self.st[0] > 1:
                self.space.add([- ((self.st[1] - self.st[0]) // 2), 0])
            return 0
        else:
            add_index = node[1] - node[0]
            index = self.st.bisect(add_index)
            if index == len(self.st):
                self.st.add(add_index)
                if self.st[-1] - self.st[-2] > 1:
                    self.space.add([-((self.st[-1] - self.st[-2]) // 2), self.st[-2]])
            else:
                self.st.add(add_index)
                next_index = index + 1
                pref_index = index - 1
                if self.st[next_index] - self.st[index] > 1:
                    self.space.add([- ((self.st[next_index] - self.st[index]) // 2), self.st[index]])
                if self.st[index] - self.st[pref_index] > 1:
                    self.space.add([-((self.st[index] - self.st[pref_index]) // 2), self.st[pref_index]])
            return add_index

    def leave(self, p):
        """
        :type p: int
        :rtype: None
        """
        index = self.st.index(p)
        if len(self.st) == 1:
            self.st = sortedcontainers.SortedList()
            self.space = sortedcontainers.SortedList()
        else:
            if index == len(self.st) - 1:
                last_index = index - 1
                if self.st[index] - self.st[last_index] > 1:
                    self.space.remove([-((self.st[index] - self.st[last_index]) // 2), self.st[last_index]])
                if self.st[index] < self.n - 1:
                    self.space.remove([- self.n + 1 + self.st[index], self.st[index]])
                self.space.add([- self.n + 1 + self.st[last_index], self.st[last_index]])
                self.st.pop(index)
            else:
                if index == 0:
                    next_index = index + 1
                    if self.st[next_index] - self.st[index] > 1:
                        self.space.remove([-((self.st[next_index] - self.st[index]) // 2), self.st[index]])
                    if self.st[index] > 0:
                        self.space.remove([- self.st[index], -1])
                    self.space.add([-self.st[next_index], -1])
                    self.st.pop(index)
                else:
                    next_index = index + 1
                    last_index = index - 1
                    if self.st[next_index] - self.st[index] > 1:
                        self.space.remove([-((self.st[next_index] - self.st[index]) // 2), self.st[index]])
                    if self.st[index] - self.st[last_index] > 1:
                        self.space.remove([-((self.st[index] - self.st[last_index]) // 2), self.st[last_index]])
                    self.space.add([- ((self.st[next_index] - self.st[last_index]) // 2), self.st[last_index]])
                    self.st.pop(index)


obj = ExamRoom(10)
print(obj.seat())
print(obj.seat())
print(obj.seat())
print(obj.seat())

